import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-06-06
 * Time: 19:57
 */
public class test2 {
    public static int evaluate(String expression) {
        Stack<Integer> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (c == ' ') continue; // 忽略空格

            // 处理数字（整数）
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    num = num * 10 + (expression.charAt(i++) - '0');
                }
                i--; // 回退到最后一个处理的字符
                operandStack.push(num);
                continue;
            }

            // 处理运算符或括号
            switch (c) {
                case '(':
                    operatorStack.push(c);
                    break;
                case ')':
                    while (!operatorStack.peek().equals('(')) {
                        calculate(operandStack, operatorStack);
                    }
                    operatorStack.pop(); // 弹出左括号
                    break;
                case '+':
                case '-':
                case '*':
                case '/':
                    while (!operatorStack.isEmpty() && getPriority(operatorStack.peek()) >= getPriority(c)) {
                        calculate(operandStack, operatorStack);
                    }
                    operatorStack.push(c);
                    break;
                default:
                    throw new IllegalArgumentException("非法字符: " + c);
            }
        }

        // 处理剩余运算符
        while (!operatorStack.isEmpty()) {
            calculate(operandStack, operatorStack);
        }

        return operandStack.pop();
    }

    private static int getPriority(char op) {
        if (op == '*' || op == '/') return 2;
        if (op == '+' || op == '-') return 1;
        return 0; // 括号优先级（不参与计算）
    }

    private static void calculate(Stack<Integer> operandStack, Stack<Character> operatorStack) {
        if (operandStack.size() < 2 || operatorStack.isEmpty()) {
            throw new IllegalArgumentException("表达式格式错误");
        }
        int b = operandStack.pop();
        int a = operandStack.pop();
        char op = operatorStack.pop();
        int result = 0;

        switch (op) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                if (b == 0) throw new ArithmeticException("除数不能为0");
                result = a / b; // 整数除法，向下取整
                break;
            default:
                throw new IllegalArgumentException("未知运算符: " + op);
        }
        operandStack.push(result);
    }

    public static void main(String[] args) {
        String expr = "3+4*(2-1)/2";
        System.out.println("表达式: " + expr);
        System.out.println("结果: " + evaluate(expr)); // 输出: 5
    }
}
